﻿// 0811train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

/*
给你一个整数数组 coins ，表示不同面额的硬币；
以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。
如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
 */

int solve01(vector<int>&coins, int amount)
{
	//边界条件
	//dp[i][0]=0 dp[0][w]=0

	//转移方程
	//dp[i][w]=min(dp[i][w], 1+dp[i][w-curr_w]
	int dp_size = coins.size() + 1;
	int amount_size = amount + 1;
	//目标：最小硬币数量（初始化为最大）
	vector<int>amount_vec(amount_size, amount+1);
	vector<vector<int>>dynamic_grid(dp_size, amount_vec);

	for (int i=0;i<dp_size; i++)
	{
		//边界条件，非常重要
		//amount==0是可以实现的，所有硬币都不取就可以了
		//结果是0枚硬币
		dynamic_grid[i][0] = 0;
	}

	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<amount_size; w++)
		{
			int curr_w = coins[i-1];
			if (w<curr_w)
			{
				//不取curr_w, 继承
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				//子集有解时，才选择子集1+dynamic_grid[i][w-curr_w]
				dynamic_grid[i][w] = min(dynamic_grid[i][w], 1+dynamic_grid[i][w - curr_w]);
			}
		}

	}

	int result = dynamic_grid[dp_size - 1][amount];
	if (result==amount+1)
	{
		return -1;
	}
	return result;
	//solve01
}


/*
 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
 */

int solve02(int amount, vector<int>&coins)
{
	int dp_size = coins.size() + 1;
	int amount_size = amount + 1;
	vector<int>amount_vec(amount_size, 0);
	vector<vector<int>>dynamic_grid(dp_size, amount_vec);
	//边界条件
	//amount为0,只有1种取法
	//dp[i][0]=1
	//前0个数，0种取法
	//dp[0][w]=0
	for (int i=0; i<dp_size; i++)
	{
		dynamic_grid[i][0] = 1;
	}
	//转移方程int curr_w = coins[i-1]
	//dp[i][w]=dp[i-1][w]+dp[i][w-curr_w]
	for (int i=1; i<dp_size; i++)
	{
		for (int w=0; w<amount_size; w++)
		{
			int curr_w = coins[i - 1];
			if (w<curr_w)
			{
				//curr_w不取，继承i-1
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				//curr_w不取+取(前i个数，凑出w-curr_w)
				dynamic_grid[i][w] = dynamic_grid[i - 1][w] + dynamic_grid[i][w - curr_w];
			}
		}
	}
	return dynamic_grid[dp_size - 1][amount];

	//solve02
}


/*
给你一个 只包含正整数 的 非空 数组 nums
请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 */

bool solve03(vector<int>&nums)
{
	//目标，数组能否凑出sum/2
	//边界条件,可以凑出0，全不取,前0个数凑不成w
	//dp[i][0]=true dp[0][w]=false
	//转移方程(不取curr_w或者取)
	//dp[i][w]=dp[i-1][w]||dp[i-1][w-curr_w]

	int sum = 0;
	for (auto&num:nums)
	{
		sum += num;
	}
	if (sum%2!=0)
	{
		//奇数不可能分成两个相等
		return false;
	}
	sum = sum / 2;

	int dp_size = nums.size() + 1;
	int sum_size = sum + 1;
	vector<int>sum_vec(sum_size, false);
	vector<vector<int>>dynamic_grid(dp_size, sum_vec);
	for (int i=0; i<dp_size; i++)
	{
		dynamic_grid[i][0] = true;
	}

	for (int i=1; i<dp_size; i++)
	{
		for (int w=1; w<sum_size; w++)
		{
			//dp[i][w]=dp[i-1][w]||dp[i-1][w-curr_w]
			int curr_w = nums[i - 1];
			if (w<curr_w)
			{	//不取curr_w
				dynamic_grid[i][w] = dynamic_grid[i - 1][w];
			}
			else
			{
				dynamic_grid[i][w] = dynamic_grid[i - 1][w] || dynamic_grid[i-1][w-curr_w];
			}
		}
	}

	return dynamic_grid[dp_size - 1][sum];
	//solve03
}


int main()
{
	{
		//nums = [1,5,11,5] true
		vector<int>nums = { 1,5,11,5 };

		cout << solve03(nums);
		return 0;
	}

	{
		//amount = 5, coins = [1, 2, 5]
		int amount = 5;
		vector<int>coins = { 1,2,5 };
		cout << solve02(amount, coins);
		return 0;
	}

	//coins = [1, 2, 5], amount = 11 3
	vector<int>coins = { 1, 2, 5 };
	int amount = 11;
	cout << solve01(coins, amount);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
